1. Field of the Invention
The present invention relates to a method and routing system for the dynamic routing of traffic in a communication network wherein the dynamic alternate routing. is adapted to the traffic load present in the network such that network throughput is optimized.
2. Description of the Prior Art
In a fully meshed non-hierarchical network with n network nodes, for each origin-destination pair, there exists n-2 alternative paths having only 2 path segments. Of these alternative paths, of which there are a network-wide total of nxc3x97(nxe2x88x921)xc3x97(nxe2x88x922), and given an unevenly loaded network, some paths are underloaded and some paths are overloaded.
Non-hierarchically organized line-switching communication networks require a dynamic alternate routing that is adapted to the traffic load respectively present in the network in such a way that the network throughput is optimized. In particular, uneven load situations must be relieved by the alternate routing.
As in conventional alternate routing in hierarchical networks, with a dynamic alternate routing the attempt is first made to set up connections via one or more planned paths, which are, for the most part, direct paths. If this is not possible, because, for example all connection line bundles of the direct path are completely occupied, alternative paths are assigned to the overflow traffic.
In the selection of the alternative paths, the difference in principle is between dynamic and conventional alternate routing. In conventional alternate routing, administratively defined alternative paths are searched in a fixed sequence for an unoccupied line or, respectively, an unoccupied channel (xe2x80x9cfixed alternate routingxe2x80x9d). This pursuant to this method, the alternate routing reacts substantially insufficiently to unplanned, unusual load situations.
In dynamic alternate routing, occurrent overflow traffic is assigned to one or more active alternative,paths. This active alternate path or paths are not fixed. Rather they are selected according to the respective method for dynamic alternate routing or are newly determined for each call. The advantages of dynamic alternate routing are its robustness and flexibility in relation to uneven load situations in the network which can arise for example due to chronologically fluctuating loads (spatially limited rigid traffic incidence, e.g. in catastrophes) and network degradation (connection line bundle failures, failures of switching units). In addition, uncertainties in the network planning can be better compensated.
Central state-controlled (dynamic) routing methods are supported by a network-central processor that receives information about the present local load situation from the network nodes. Advantageous, underloaded paths can be determined centrally in this way, and the network nodes can be notified accordingly. Among other things, disadvantages include the large expense for network central stations, data transmission and the additional computing capacity required in the network nodes.
Decentral state-controlled (dynamic) methods (see e.g. EP 0 449 480 A3, EP 0 376 556 A3) are based on the reporting back of load states of the trunk groups to the origin node of the non-hierarchical (sub-)network. These methods have the disadvantage in that the non-standardized interface between the network nodes requires a homogenous network (e.g., network node of only one manufacturer) and, moreover, a high signaling expense is required.
Decentral event-controlled (dynamic) routing methods (see, e.g., EP0 339 494 B1) can achieve an increase in performance in that they learn the respective load situation by evaluating the congestion events. These methods use the congestion information (blocking event information) in order to replace the blocked path with another path. However, no distinction is thereby made between sporadic blockings (caused by static fluctuations of the offered traffic) and almost completed blocking (caused by uneven loading or partial network overload). A further decentral event-controlled method is known from European application EP 0 696 147 A1 (SAG-internal 94P1542E).
In a high-load situation, it can occur that the path fan becomes smaller very rapidly, wherein a reinitialization occurs very quickly. Since, in this case, the path fan is refilled again with alternative paths that were previously removed, it can occur that alternative paths previously removed very recently again can be incorporated into the path fan. Since the probability is high that the load of these alternative paths has hardly changed in this short time period the path fan will again become small very rapidly, and a new reinitialization accurs soon. This process greatly reduces the performance of the method, in particular given high loading.
By means of the present invention, therefore highly-loaded alternative paths are prevented from being offered again for overload traffic too soon after their removal from the path fan and, thus, from again receiving traffic even though alternative paths already removed for a longer time would again offer sufficient capacity.
Accordingly, in an embodiment of the present invention, a method is provided for dynamic traffic routing in a communication network, wherein the method includes the steps of: initially offering calls between an origin switching node and a destination switching node to one or more preferred paths (planned paths); offering calls to alternative paths contained in a path fan, according to a particular selection scheme, for the case in which none of the planned paths is available; removing an alternative path previously contained in the path fan from the path fan as soon as, upon offering of a call, it is determined that it is no longer available; registering the chronological sequence by which the alternative paths are removed from the path fan; and reinitializing the path fan after the introduction of a particular event and/or fulfillment of a particular condition, by refilling it with previously removed alternative paths, wherein the path fan is refilled with the alternative paths that, according to the chronological sequence, have already been removed from the path fan for the longest time.
In an embodiment, the method further includes the steps of: offering overflow calls, up to a predetermined maximum number, to an alternative path selected from the path fan for the overflow traffic, before a transition is made to the alternative path that is next according to the named selection scheme; counting the number of calls offered to the alternative path up to a possible determination of non-availability; incorporating, given a determination of non-availability of the alternative path, this path into a first passive set of alternative paths if the named number is less than a particular value; incorporating this path into a second passive set of alternative paths if the named number reaches or exceeds the particular value; and reinitializing the path fan such that alternative paths that come from the first passive set and have already been removed from the path fan for the longest time are again incorporated into the path fan, and, if these do not suffice to refill the path fan, alternative paths that come from the second passive set and have already been removed from the path fan for the longest time are also incorporated into the path fan.
Additional features and advantages of the present invention are described in, and will be apparent from, the Detailed Description of the Preferred Embodiments and the Drawing.